(in-package "ACL2")

(include-book "io-utilities" :dir :teachpacks)
(include-book "list-utilities" :dir :teachpacks)
(include-book "binary-io-utilities" :dir :teachpacks)

(include-book "formulas")

(include-book "modified-avl-rational-keys-inner")
(include-book "modified-avl-rational-keys-outer")

(include-book "world" :dir :teachpacks)

(include-book "sum-list")
(include-book "trim-string")
(include-book "list-defuns")
;(include-book "merge-sort")

(defconst *K* 48)
(defconst *MIN-GPA* 2)
(defconst *MAX-GPA* 4)
(defconst *GPA-GAP/2* 0.125)
(defconst *CONVERTED-GRADE-LENGTH*
  (/ (- *MAX-GPA* *MIN-GPA*) (* *GPA-GAP/2* 2)))

(defconst *FEMALE* "f")
(defconst *MALE* "m")
(defconst *GENDER-LIST* (list *FEMALE* *MALE*))
(defconst *UPPER-BOUND-FOR-LOW-GENDER-PERCENTAGE* 0.33)
(defconst *NO-SUFFICIENT-LOW-PERCENTAGE-GENDER* "N/A")

(defconst *NO-SUB-WEIGHT-INPUT* "NO SUB-WEIGHT INPUT")

(defconst *INVALID-INPUT-SPECIFICATION-LINE*
  "INVALID INPUT IN SPECIFICATION LINE!")
(defconst *INVALID-GENDER-INPUT*
  "INVALID GENDER INPUT!")

(defconst *UNKNOWN-ERROR* "UNKNOWN ERROR!!!")
(defconst *SKILL-SET* "SKILL SET")
 
(defun transpose-fast-aux (matrix)
  (if (endp matrix)
      (mv nil nil)
    
    (let ((element-to-append (caar matrix))
          (new-row (cdar matrix)))
      
      (mv-let (acc new-row-list)
              (transpose-fast-aux (cdr matrix))
              (mv (cons element-to-append acc)
                  (cons new-row new-row-list))))))

(defun transpose-fast (matrix)
  (if (endp (car matrix))
      nil
    (mv-let (new-row remaining-matrix)
            (transpose-fast-aux matrix)
            (cons new-row
                  (transpose-fast remaining-matrix)))))

(defun split (n xs)
  (if (and (posp n) (consp xs))
      (let* ((x (car xs))
            (s (split (- n 1) (cdr xs)))
            (fr (car s))
            (bk (cadr s)))
        (list (cons x fr) bk))
      (list nil xs)))

(defun merge (xs ys)         ; assume xs and ys are sorted
   (let ((x (car xs))
          (sx (cdr xs))
          (y (car ys))
          (sy (cdr ys)))
       (cond
         ((endp xs) ys)
         ((endp ys) xs)
         ((< (cadr x) (cadr y))
              (cons x (merge sx ys)))
         (t
              (cons y (merge xs sy))))))

(defun merge-sort (xs)
  (if (consp (cdr xs))
      (let ((halves (split (floor (len xs) 2) xs)))
          (merge (merge-sort (car halves))
                 (merge-sort (cadr halves))))
      xs))

(defun get-total-weight (list-of-input-weights)
  (if (rational-listp list-of-input-weights)
      (if (consp list-of-input-weights)
          (+ (abs (car list-of-input-weights))
             (get-total-weight (cdr list-of-input-weights)))
          0)
      list-of-input-weights))

(defun get-list-of-actual-weights
  (list-of-input-weights total-weight)
  (if (posp total-weight)
      (if (consp list-of-input-weights)
          (cons (/ (car list-of-input-weights)
                   total-weight)
                (get-list-of-actual-weights (cdr list-of-input-weights)
                                            total-weight))
          nil)
      list-of-input-weights))

(defun get-considered-skill-sets-as-strs
  (skill-set-specification-str-down-case)
  (map-chrs->str (remove nil (packets #\; (str->chrs 
                                           skill-set-specification-str-down-case)))))

(defun digit-chars-p
  (chrs)
  (if (consp chrs)
      (and (digit-char-p (car chrs))
           (digit-chars-p (cdr chrs)))
      t))

(defun get-input-considered-skill-sets
  (considered-skill-sets-as-strs)
  (if (consp considered-skill-sets-as-strs)
      (let* ((first-considered-skill-set-str
              (car considered-skill-sets-as-strs))
             (user-did-input-skill-set-name
              (member-equal #\: (str->chrs first-considered-skill-set-str)))
             (first-considered-skill-set-data
              (map-chrs->str (remove nil (packets #\, (str->chrs first-considered-skill-set-str)))))
             (first-ele-in-first-considered-skill-set-data
              (car first-considered-skill-set-data))
             (rest-considered-skill-sets
              (get-input-considered-skill-sets (cdr considered-skill-sets-as-strs))))
        (if first-ele-in-first-considered-skill-set-data
            (let* (
             (user-did-input-sub-weight
              (digit-chars-p (str->chrs (trim first-ele-in-first-considered-skill-set-data)))))
        (cond 
          ((and user-did-input-sub-weight
                user-did-input-skill-set-name)
           (let* ((first-considered-skill-set-sub-weight
                   (str->rat first-ele-in-first-considered-skill-set-data))
                  (first-considered-skill-set-name-and-first-skill
                    (map-chrs->str
                     (remove nil
                             (packets #\:
                                      (str->chrs (cadr first-considered-skill-set-data))))))
                  (first-ele-in-first-considered-skill-set-name-and-first-skill
                   (car first-considered-skill-set-name-and-first-skill))
                  (first-considered-skill-set-name
                   (if first-ele-in-first-considered-skill-set-name-and-first-skill
                       (trim first-ele-in-first-considered-skill-set-name-and-first-skill)
                       *SKILL-SET*))
                  (second-ele-in-first-considered-skill-set-name-and-first-skill
                   (cadr first-considered-skill-set-name-and-first-skill))
                  (first-considered-skill-set-data-but-first-two
                   (cddr first-considered-skill-set-data))
                  (first-considered-skill-set
                   (cond
                     ((and second-ele-in-first-considered-skill-set-name-and-first-skill
                           first-considered-skill-set-data-but-first-two)
                      (trim-list-of-strs 
                       (cons second-ele-in-first-considered-skill-set-name-and-first-skill
                             first-considered-skill-set-data-but-first-two)))
                     ((and second-ele-in-first-considered-skill-set-name-and-first-skill
                           (not first-considered-skill-set-data-but-first-two))
                      (list (trim second-ele-in-first-considered-skill-set-name-and-first-skill)))
                     ((and (not second-ele-in-first-considered-skill-set-name-and-first-skill)
                           first-considered-skill-set-data-but-first-two)
                      (trim-list-of-strs first-considered-skill-set-data-but-first-two)))))
             (if first-considered-skill-set
                 (cons (list first-considered-skill-set-name
                             first-considered-skill-set-sub-weight
                             first-considered-skill-set)
                       rest-considered-skill-sets)
                 rest-considered-skill-sets)))
          
         ((and user-did-input-sub-weight
               (not user-did-input-skill-set-name))
          (let* ((first-considered-skill-set-sub-weight-no-name
                  (str->rat first-ele-in-first-considered-skill-set-data))
                 (first-considered-skill-set-no-name
                  (trim-list-of-strs (cdr first-considered-skill-set-data))))
            (if first-considered-skill-set-no-name
                (cons (list *SKILL-SET*
                             first-considered-skill-set-sub-weight-no-name
                             first-considered-skill-set-no-name)
                       rest-considered-skill-sets)
                 rest-considered-skill-sets)))
         
         ((and (not user-did-input-sub-weight)
               user-did-input-skill-set-name)
          (let* ((first-considered-skill-set-name-and-first-skill-no-weight
                  (map-chrs->str
                   (remove nil
                           (packets #\:
                           (str->chrs first-ele-in-first-considered-skill-set-data)))))
                  (first-ele-in-first-considered-skill-set-name-and-first-skill-no-weight
                   (car first-considered-skill-set-name-and-first-skill-no-weight))
                  (first-considered-skill-set-name-no-weight
                   (if first-ele-in-first-considered-skill-set-name-and-first-skill-no-weight
                       (trim first-ele-in-first-considered-skill-set-name-and-first-skill-no-weight)
                       *SKILL-SET*))
                  (second-ele-in-first-considered-skill-set-name-and-first-skill-no-weight
                   (cadr first-considered-skill-set-name-and-first-skill-no-weight))
                  (first-considered-skill-set-data-but-first
                   (cdr first-considered-skill-set-data))
                  (first-considered-skill-set-no-weight
                   (cond
                     ((and second-ele-in-first-considered-skill-set-name-and-first-skill-no-weight
                           first-considered-skill-set-data-but-first)
                      (trim-list-of-strs (cons second-ele-in-first-considered-skill-set-name-and-first-skill-no-weight
                                               first-considered-skill-set-data-but-first)))
                     ((and second-ele-in-first-considered-skill-set-name-and-first-skill-no-weight
                           (not first-considered-skill-set-data-but-first))
                      (list (trim second-ele-in-first-considered-skill-set-name-and-first-skill-no-weight)))
                     ((and (not second-ele-in-first-considered-skill-set-name-and-first-skill-no-weight)
                           first-considered-skill-set-data-but-first)
                      (trim-list-of-strs first-considered-skill-set-data-but-first)))))
             (if first-considered-skill-set-no-weight
                 (cons (list first-considered-skill-set-name-no-weight
                             *NO-SUB-WEIGHT-INPUT*
                             first-considered-skill-set-no-weight)
                       rest-considered-skill-sets)
                 rest-considered-skill-sets)))
         (t
          (cons (list *SKILL-SET*
                      *NO-SUB-WEIGHT-INPUT*
                      (trim-list-of-strs first-considered-skill-set-data))
                rest-considered-skill-sets))))
            rest-considered-skill-sets))
      considered-skill-sets-as-strs))

(defun set-default-sub-weights-for-skill-sets
  (input-sub-weights-of-skill-sets)
  (if (consp input-sub-weights-of-skill-sets)
      (let ((first-input-sub-weight
             (car input-sub-weights-of-skill-sets))
            (rest-default-sub-weights
             (set-default-sub-weights-for-skill-sets
              (cdr input-sub-weights-of-skill-sets))))
        (if (or (equal first-input-sub-weight
                       *NO-SUB-WEIGHT-INPUT*)
                (= first-input-sub-weight 0))
            rest-default-sub-weights
            (cons first-input-sub-weight
                  rest-default-sub-weights)))
      nil))

(defun get-actual-sub-weights-of-skill-sets
  (input-sub-weights-of-skill-sets)
  (if (consp input-sub-weights-of-skill-sets)
      (let ((num-skill-sets
             (len input-sub-weights-of-skill-sets)))
        (if (not (drop-set (list *NO-SUB-WEIGHT-INPUT*)
                           input-sub-weights-of-skill-sets))
            (replicate num-skill-sets
                       (/ 1 num-skill-sets))
            (let ((default-sub-weights-for-skill-sets
                    (set-default-sub-weights-for-skill-sets
                     input-sub-weights-of-skill-sets)))
              (get-list-of-actual-weights default-sub-weights-for-skill-sets
                                          (get-total-weight
                                           default-sub-weights-for-skill-sets)))))
      nil))

(defun pairs (xs ys zs)
  (if (and (consp xs) (consp ys) (consp zs))
      (cons (list (car xs) (car ys) (car zs))
            (pairs (cdr xs) (cdr ys) (cdr zs)))
      nil))

(defun get-converted-skill-set-specifications
  (input-skill-sets)
  (if (consp input-skill-sets)
      (let* ((skill-set-names
             (strip-cars input-skill-sets))
             (input-sub-weights-of-skill-sets
              (strip-cars (strip-cdrs input-skill-sets)))
             (actual-sub-weights-of-skill-sets
              (get-actual-sub-weights-of-skill-sets input-sub-weights-of-skill-sets))
             (skill-sets
              (strip-cars (strip-cdrs (strip-cdrs input-skill-sets)))))
        (pairs skill-set-names
               actual-sub-weights-of-skill-sets
               skill-sets))
      nil))

(defun get-list-of-all-team-member-data-by-criterion
  (team-flatten-avl)
  (if (consp team-flatten-avl)
      (transpose-fast
       (strip-cdrs team-flatten-avl))
      nil))

(defun binary-or (list-of-1s-and-0s)
  (if (consp list-of-1s-and-0s)
      (if (= (car list-of-1s-and-0s) 1)
          1
          (binary-or
           (cdr list-of-1s-and-0s)))
      0))

(defun calculate-team-schedule-score-aux
  (list-of-team-member-time-avalability-transpose)
  (if (consp list-of-team-member-time-avalability-transpose)
      (cons (- 1
               (binary-or
                (car list-of-team-member-time-avalability-transpose)))
            (calculate-team-schedule-score-aux
             (cdr list-of-team-member-time-avalability-transpose)))
      nil))

(defun calculate-team-schedule-score
  (list-of-all-team-member-data-by-criterion schedule-weight)
  (if (not (or (endp list-of-all-team-member-data-by-criterion)
               (zerop schedule-weight)))
      (* (max (/ (sum-list
                  (calculate-team-schedule-score-aux
                   (transpose-fast
                    (car (cddddr
                          list-of-all-team-member-data-by-criterion)))))
                 *K*)
              1)
         schedule-weight)
      0))

;GPA Heuristic

(defun convert-gpa
  (gpa)
  (round (/ (- gpa *MIN-GPA*) *GPA-GAP/2*) 2))

(defun get-list-of-team-member-converted-gpa-aux
  (list-of-team-member-gpa)
  (if (consp list-of-team-member-gpa)
      (cons (update-nth (convert-gpa (car list-of-team-member-gpa))
                        1
                        (replicate *CONVERTED-GRADE-LENGTH* 0))
            (get-list-of-team-member-converted-gpa-aux
             (cdr list-of-team-member-gpa)))
      nil))

(defun get-list-of-team-member-converted-gpa
  (list-of-all-team-member-data-by-criterion)
  (if (consp list-of-all-team-member-data-by-criterion)
      (get-list-of-team-member-converted-gpa-aux
       (caddr list-of-all-team-member-data-by-criterion))
      nil))

(defun calculate-team-gpa-score-aux
  (list-of-team-member-converted-gpa-transpose)
  (if (consp list-of-team-member-converted-gpa-transpose)
      (cons
       (binary-or (car list-of-team-member-converted-gpa-transpose))
       (calculate-team-gpa-score-aux
        (cdr list-of-team-member-converted-gpa-transpose)))
      nil))

(defun calculate-team-gpa-score
  (list-of-all-team-member-data-by-criterion num-of-members gpa-weight)
  (if (not (or (endp list-of-all-team-member-data-by-criterion)
               (zerop gpa-weight)))
      (*
       (/
        (sum-list (calculate-team-gpa-score-aux
                   (transpose-fast
                    (get-list-of-team-member-converted-gpa
                     list-of-all-team-member-data-by-criterion))))
        num-of-members)
       gpa-weight)
      0))

;Gender heuristic

(defun get-team-low-percentage-gender
  (list-of-team-member-genders num-of-members)
  (if (consp list-of-team-member-genders)
      (let ((female-percentage
            (/ (occurrences-equal *FEMALE* list-of-team-member-genders)
               num-of-members))
            (male-percentage
             (/ (occurrences-equal *MALE* list-of-team-member-genders)
                num-of-members)))
      (cond ((< female-percentage *UPPER-BOUND-FOR-LOW-GENDER-PERCENTAGE*)
             *FEMALE*)
            ((< male-percentage *UPPER-BOUND-FOR-LOW-GENDER-PERCENTAGE*)
             *MALE*)
            (t
            *NO-SUFFICIENT-LOW-PERCENTAGE-GENDER*)))
      *UNKNOWN-ERROR*))

(defun convert-gender
  (gender low-percentage-gender)
  (if (string-equal gender low-percentage-gender)
      1
      0))
       
(defun get-list-of-team-member-gender-converted
  (list-of-team-member-genders low-percentage-gender)
  (if (consp list-of-team-member-genders)
      (cons (convert-gender
             (car list-of-team-member-genders)
             low-percentage-gender)
            (get-list-of-team-member-gender-converted
             (cdr list-of-team-member-genders)
             low-percentage-gender))
      nil))

(defun calculate-team-gender-score
  (list-of-all-team-member-data-by-criterion num-of-members gender-weight)
   (if (not (or (endp list-of-all-team-member-data-by-criterion)
                (zerop gender-weight)))
      (let* ((list-of-team-member-gender
              (cadr list-of-all-team-member-data-by-criterion))
             (low-percentage-gender
              (get-team-low-percentage-gender list-of-team-member-gender
                                              num-of-members)))
        (if (equal low-percentage-gender
                   *NO-SUFFICIENT-LOW-PERCENTAGE-GENDER*)
            gender-weight
            (let* ((list-of-team-member-gender-converted
                    (get-list-of-team-member-gender-converted list-of-team-member-gender
                                                              low-percentage-gender))
                   (sum-gender
                    (sum-list list-of-team-member-gender-converted))
                   (heuristic-result
                    (cond ((>= sum-gender 2) 1)
                          ((= sum-gender 1) -1)
                          ((= sum-gender 0) 0))))
              (* heuristic-result gender-weight))))
      0))

;; Skill sets Heuristic

(defun read-individual-input-skill-sets
  (individual-skill-sets-as-strs)
   (if (consp individual-skill-sets-as-strs)
       (let* ((individual-first-skill-set-as-str
               (car individual-skill-sets-as-strs))
              (individual-first-skill-set
               (trim-list-of-strs 
                (map-chrs->str
                 (remove nil 
                         (packets #\, 
                                  (str->chrs individual-first-skill-set-as-str)))))))
         (cons individual-first-skill-set
               (read-individual-input-skill-sets (cdr individual-skill-sets-as-strs))))
       nil))

(defun read-all-team-member-input-skill-sets
  (all-team-member-input-skill-sets-as-strs)
  (if (consp all-team-member-input-skill-sets-as-strs)
      (let* ((first-team-member-skill-sets-as-str
              (car all-team-member-input-skill-sets-as-strs))
             (first-team-member-skill-sets-as-strs
              (trim-list-of-strs 
               (map-chrs->str
                (remove nil 
                        (packets #\;
                                 (str->chrs first-team-member-skill-sets-as-str))))))
             (first-team-member-input-skill-sets
              (read-individual-input-skill-sets first-team-member-skill-sets-as-strs)))
        (cons first-team-member-input-skill-sets
              (read-all-team-member-input-skill-sets
               (cdr all-team-member-input-skill-sets-as-strs))))
      nil))

(defun which-considered-skill-set-aux
  (skill considered-skill-sets n)
  (if (consp considered-skill-sets)
      (if (member-equal skill
                        (car considered-skill-sets))
          n
          (which-considered-skill-set-aux skill
                                          (cdr considered-skill-sets)
                                          (1+ n)))
      -1))

(defun which-considered-skill-set
  (member-skills considered-skill-sets)
  (if (consp member-skills)
      (let ((of-skill-set-base-on-first-skill
             (which-considered-skill-set-aux (car member-skills)
                                             considered-skill-sets
                                             0)))
        (if (= of-skill-set-base-on-first-skill
               -1)
            (which-considered-skill-set (cdr member-skills)
                                        considered-skill-sets)
            of-skill-set-base-on-first-skill))
      -1))

(defun get-all-team-member-skills-by-skill-set-position-aux
  (individual-skill-sets converted-skill-sets)
  (if (consp individual-skill-sets)
      (let* ((individual-first-skill-set
              (car individual-skill-sets))
             (first-skill-set-is-of
              (which-considered-skill-set (car individual-skill-sets)
                                          converted-skill-sets))
             (individual-skill-sets-but-first
              (cdr individual-skill-sets))
             (rest-skill-sets-are-of
              (get-all-team-member-skills-by-skill-set-position-aux
               (cdr individual-skill-sets)
               converted-skill-sets))) 
          (if (= first-skill-set-is-of
                 -1)
              rest-skill-sets-are-of
              (cons (list individual-first-skill-set
                          first-skill-set-is-of)
                    rest-skill-sets-are-of)))
      nil))

(defun get-all-team-member-skills-by-skill-set-position
  (team-skill-sets considered-skill-sets)
  (if (consp team-skill-sets)
      (append (get-all-team-member-skills-by-skill-set-position-aux
               (car team-skill-sets)
               considered-skill-sets)
              (get-all-team-member-skills-by-skill-set-position (cdr team-skill-sets)
                                                                considered-skill-sets))
      nil))

(defun convert-individual-skill-set-aux
  (individual-skills considered-skill-set converted-skills)
  (if (consp individual-skills)
      (let* ((first-skill
              (car individual-skills))
             (first-skill-position
             (position-equal first-skill
                             considered-skill-set))
             (updated-converted-skills
              (if first-skill-position
                  (update-nth first-skill-position 
                              1 
                              converted-skills)
                  converted-skills)))
        (convert-individual-skill-set-aux (cdr individual-skills)
                                          considered-skill-set
                                          updated-converted-skills))
      converted-skills))

(defun convert-all-team-member-skill-set
  (all-team-member-skills-of-skill-set considered-skill-set)
  (if (consp all-team-member-skills-of-skill-set)
      (let* ((first-team-member-skill
              (car all-team-member-skills-of-skill-set))
             (considered-skill-set-len
              (len considered-skill-set))
             (converted-skill-set
              (replicate considered-skill-set-len
                         0)))
        (cons (convert-individual-skill-set-aux first-team-member-skill
                                                considered-skill-set
                                                converted-skill-set)
              (convert-all-team-member-skill-set
               (cdr all-team-member-skills-of-skill-set)
               considered-skill-set)))
      nil))

(defun calculate-team-skill-set-score-aux
  (converted-all-team-member-skills-of-first-considered-skill-set-transpose)
  (if (consp converted-all-team-member-skills-of-first-considered-skill-set-transpose)
      (let* ((all-team-member-skills-of-first-considered-skill-set
              (car converted-all-team-member-skills-of-first-considered-skill-set-transpose))
             (sum-of-all-team-member-first-skill-of-skill-set
              (sum-list all-team-member-skills-of-first-considered-skill-set))
             (d-square
              (if (<= sum-of-all-team-member-first-skill-of-skill-set
                      1)
                  0
                  (* sum-of-all-team-member-first-skill-of-skill-set
                     sum-of-all-team-member-first-skill-of-skill-set))))
        (cons d-square
              (calculate-team-skill-set-score-aux 
               (cdr converted-all-team-member-skills-of-first-considered-skill-set-transpose))))
      nil))

(defun calculate-team-skill-set-score
  (converted-all-team-member-skills-of-first-considered-skill-set
   num-of-members
   num-of-considered-skills-in-skill-set
   skill-set-actual-subweight)
  (if (not (or (endp converted-all-team-member-skills-of-first-considered-skill-set)
               (zerop skill-set-actual-subweight)))
      (* (max (- 1 
                 (/ (sum-list
                     (calculate-team-skill-set-score-aux
                      (transpose-fast
                       converted-all-team-member-skills-of-first-considered-skill-set)))
                    (* num-of-members
                       num-of-considered-skills-in-skill-set)))
              0)
         skill-set-actual-subweight)
      0))

(defun calculate-all-team-member-skill-sets-scores
  (all-team-member-skills-by-skill-set-with-position-sorted
   num-of-members
   considered-skill-sets-specifications)
  (if (and (consp considered-skill-sets-specifications)
           (consp all-team-member-skills-by-skill-set-with-position-sorted))
      (let* ((all-team-member-skills-by-skill-set
              (strip-cars all-team-member-skills-by-skill-set-with-position-sorted))
             (all-team-member-skills-by-skill-set-position
              (strip-cars
               (strip-cdrs all-team-member-skills-by-skill-set-with-position-sorted)))
             (first-considered-skill-set-by-position
              (car all-team-member-skills-by-skill-set-position))
             (first-considered-skill-set-data
              (nth first-considered-skill-set-by-position considered-skill-sets-specifications))
             (first-considered-skill-set
              (caddr first-considered-skill-set-data))
             (first-considered-skill-set-actual-subweight
              (cadr first-considered-skill-set-data))
             (num-of-considered-skills-in-first-considered-skill-set
              (len first-considered-skill-set))
             (all-team-member-skills-by-skill-set-position-w/o-first
              (drop-set (list first-considered-skill-set-by-position)
                        all-team-member-skills-by-skill-set-position))
             (second-considered-skill-set-by-position 
              (car all-team-member-skills-by-skill-set-position-w/o-first))
             (all-team-member-skills-of-first-considered-skill-set-by-position 
              (take-to second-considered-skill-set-by-position 
                       all-team-member-skills-by-skill-set-position))
             (length
              (len all-team-member-skills-of-first-considered-skill-set-by-position))
             (all-team-member-skills-of-first-considered-skill-set
              (car 
               (break-at-nth length
                             all-team-member-skills-by-skill-set)))
             (all-team-member-skills-by-skill-set-but-first-considered-skill-set-with-position
              (cadr 
               (break-at-nth length
                             all-team-member-skills-by-skill-set-with-position-sorted)))
             (converted-all-team-member-skills-of-first-considered-skill-set
              (convert-all-team-member-skill-set all-team-member-skills-of-first-considered-skill-set
                                                 first-considered-skill-set))
             (team-first-considered-skill-set-score
              (calculate-team-skill-set-score converted-all-team-member-skills-of-first-considered-skill-set
                                              num-of-members
                                              num-of-considered-skills-in-first-considered-skill-set
                                              first-considered-skill-set-actual-subweight)))

        (cons team-first-considered-skill-set-score
              (calculate-all-team-member-skill-sets-scores 
               all-team-member-skills-by-skill-set-but-first-considered-skill-set-with-position
               num-of-members
               considered-skill-sets-specifications)))
      nil))

(defun calculate-team-skill-sets-score
  (list-of-all-team-member-data-by-criterion
   num-of-members
   considered-skill-sets-specifications
   skill-set-actual-total-weight)
  (if (not (or (endp list-of-all-team-member-data-by-criterion)
               (zerop skill-set-actual-total-weight)))
      (let* ((all-team-member-input-skill-sets-as-strs
              (cadddr list-of-all-team-member-data-by-criterion))
             (all-team-member-input-skill-sets
              (read-all-team-member-input-skill-sets all-team-member-input-skill-sets-as-strs))
             (all-team-member-skills-by-skill-set-position
              (get-all-team-member-skills-by-skill-set-position all-team-member-input-skill-sets
                                                                considered-skill-sets-specifications))
             (all-team-member-skill-sets-scores
              (calculate-all-team-member-skill-sets-scores
               (merge-sort all-team-member-skills-by-skill-set-position)
               num-of-members
               considered-skill-sets-specifications)))
        (* (sum-list all-team-member-skill-sets-scores)
           skill-set-actual-total-weight))
      0))

;--------------------------------
(defun calculate-team-score
  (team-key 
   team-flatten-avl
   list-of-actual-weights
   considered-skill-sets-specifications)
  (if (and (consp team-flatten-avl)
           (consp list-of-actual-weights)
           (consp considered-skill-sets-specifications))
  (let* ((num-of-members
          (len team-flatten-avl))
         (list-of-all-team-member-data-by-criterion
          (get-list-of-all-team-member-data-by-criterion team-flatten-avl))
         (actual-gpa-weight
          (car list-of-actual-weights))
         (actual-schedule-weight
          (cadr list-of-actual-weights))
         (actual-gender-weight
          (caddr list-of-actual-weights))
         (actual-skill-set-total-weight
          (cadddr list-of-actual-weights))
         (team-gpa-score
          (calculate-team-gpa-score list-of-all-team-member-data-by-criterion
                                    num-of-members
                                    actual-gpa-weight))
         (team-schedule-score
          (calculate-team-schedule-score list-of-all-team-member-data-by-criterion
                                         actual-schedule-weight))
         (team-gender-score
          (calculate-team-gender-score list-of-all-team-member-data-by-criterion
                                       num-of-members
                                       actual-gender-weight))
         (team-skill-sets-score
          (calculate-team-skill-sets-score list-of-all-team-member-data-by-criterion
                                           num-of-members
                                           considered-skill-sets-specifications
                                           actual-skill-set-total-weight)))
    
    (list team-key
          ;team-flatten-avl
          (+
           team-gpa-score
           team-schedule-score
           team-gender-score
           team-skill-sets-score)))
  0))

  (defun get-random-number (seed)
    (let ((modulo (expt 2 32))
          (multiplier 1103515245)
          (increment 12345)
         )
          (mod (+ (* multiplier seed) increment) modulo)
    )
  )
  
;get-score
;will call the method to create the scores of the function
;variables:
;  xs: (first-individual second-individual)
(defun get-score (xs)
  (cons xs 5)
  )

;create-y
;input: (create-y 110 '(111 112 113))
;output: ((110 . 111) (110 . 112) (110 . 113))
(defun create-y (x ys)
  (if (consp ys)
      (cons (list x (car ys)) (create-y x (cdr ys)))
      nil)
  )
;create=x
;input: (create-x '(110 111 112) '(113 114 115))
;output: (((110 . 113) (110 . 114) (110 . 115)) ((111 . 113) (111 . 114) (111 . 115)) ((112 . 113) (112 . 114) (112 . 115)))
(defun create-x (xs ys)
  (if (consp xs)
      (cons (create-y (car xs) ys) (create-x (cdr xs) ys))
      nil
     )
  )

;find-all-combination-helper
(defun find-all-combination-helper (xs)
  (if (consp xs)
      (cons (car xs) (find-all-combination-helper (cdr xs)))
      nil)
  )

;find-all-possible-combinations
(defun find-best-combination (xs)
  (if (consp xs)
      (cons (find-all-combination-helper (car xs)) (find-best-combination (cdr xs)))
      nil)
  )

;create-all-possible-combinations
(defun create-all-possible-combinations (xs ys)
  (find-best-combination (create-x xs ys))    
  )



;check-to-stop-switching
(defun check-to-stop-switching (member-list-1 member-list-2)
  nil
  )

;switch-member-between-teams
;parameters
;  input:  avl-tree: complete avl tree
;          worst-team-key: team with the lowest score that we need to try and improve: '(group# score)
;          random-team-key: team that does not have the lowest score but is not necessarily the highest: '(group# score)
;  output: improved avl tree with the switched team numbers
;
(defun switch-member-between-teams (avl-tree worst-team-key random-team-key)
  (avl-retrieve avl-tree worst-team-key)
  )

;compare-scores-between-team-sets-helper
;parameters
;  input:  avl-team: name of 1st team to compare
;          avl-tree: complete avl tree
;  output: returns the score of the avl-team
(defun compare-scores-between-team-sets-helper (avl-team avl-tree)
  (car (cdr (car (avl-retrieve avl-tree avl-team))))
  )

;compare-scores-between-team-sets
;parameters
;  input:  avl-team-1: name of 1st team to compare
;          avl-team-2: name of 2nd team to compare
;          avl-tree: complete avl tree
;  output: the teams avl tree with the better score
;  ex: (avl-retrieve '(2 (1 30) (test value) nil (1 (2 15) (test1 value1) nil nil)) '(1 30)) -> ((1 30) test value)
(defun compare-scores-between-team-sets (avl-team-1 avl-team-2 avl-tree)
  (if (>= (compare-scores-between-team-sets-helper avl-team-1 avl-tree)
          (compare-scores-between-team-sets-helper avl-team-2 avl-tree))
      avl-team-1
      avl-team-2)
  )

  (defun get-random-number-mod-max (seed max)
    (let ((new-seed (get-random-number seed))
         )
          (cons (mod new-seed max) new-seed)
    )
  )

(defun form-groups (list-of-students seed avl-tree)
  (if (consp list-of-students)
      (form-groups (car list-of-students) seed (avl-insert avl-tree (get-random-number-mod-max (car seed) (car (cdr seed))) (car list-of-students)))
      avl-tree
      )
  )

(defun compare-student-id (value x y)
  (if (consp x)
      (if (char-equal (car x) (car y))
          (compare-student-id t (cdr x) (cdr y))
          nil)
      value)
  )

;compare-students
;  input: 
;
; takes in a list and an item to compare.  this item to compare is the entire the student list.  will compare student id's.  returns position that student is in
(defun compare-students-and-return-pos (i x xs)
  (if (consp xs)
      (if (compare-student-id t (car x) (caar xs))
          i
          (compare-students-and-return-pos (+ i 1) x (cdr xs)))
      nil
      )
  )

;remove-nth-student-helper
(defun remove-nth-student-helper (i pos xs)
  (if (= i pos)
      nil
      (car xs)
      )
  )

;remove-nth-student
;removes the student specified
(defun remove-nth-student (i pos xs)
  (if (consp xs)
      (remove nil (cons (remove-nth-student-helper i pos xs) (remove-nth-student (+ i 1) pos (cdr xs))))
      nil
  )
)

;randomize-list
(defun randomize-list (seed list)
  (if (consp list)
      (cons (nth (car (get-random-number-mod-max seed (len list))) list)
            (randomize-list (car (get-random-number-mod-max seed (len list))) (remove-nth-student 0 (car (get-random-number-mod-max seed (len list))) list)))
      nil))


;remove-recurrences-helper
(defun remove-recurrence-helper (x ys)
  (if (consp ys)
      ;(if (not (string-equal (chrs->str (car x)) (chrs->str (caar ys))))
      ;(if (not (string-equal (chrs->str (car x)) (chrs->str (caar ys))))
      (if (not (string-equal (car x) (caar ys)))
          (cons (car ys) (remove-recurrence-helper x (cdr ys)))
          (remove-recurrence-helper x (cdr ys)))
nil))
  
;remove-recurrence
;input: (remove-recurrence (car (randomize-list 30 (get-students-as-data "input.txt"))) (randomize-list 30 (get-students-as-data "input.txt")))
(defun remove-recurrence (xs ys)
  (if (consp xs)
      (remove-recurrence (cdr xs) (remove-recurrence-helper (car xs) ys))
  ys))

;inner-iterator
; puts all items from list into avl-tree and organizes them by student id
; (inner-iterator (get-students-as-data "input.txt"))
(defun inner-iterator (inner-tree list)
  (if (consp list)
      (avl-insert-inner 
          (inner-iterator 
              inner-tree 
              (cdr list))
          ;(chrs->str (caar list))
          (caar list)
          (cdr (car list)))
      nil))

;create-initial-teams
;(avl-flatten (create-initial-teams 0 3 (empty-tree)))
;(((0 . 0) "no tree") ((1 . 0) "no tree") ((2 . 0) "no tree"))
(defun create-initial-teams (i num-teams outer-tree)
  (if (< i num-teams)
      (avl-insert (create-initial-teams 
                   (+ i 1)
                   num-teams
                   outer-tree
                   )
                  (cons i (list 0))
                  (list "no tree")
                  )
      nil))

;random-student-from-list
(defun random-student-from-list (list-of-students seed)
  (let ((first-part (car (break-at-nth (car (get-random-number-mod-max seed 
                                       (len list-of-students))) list-of-students)))
        (second-part (cdadr (break-at-nth (car (get-random-number-mod-max seed 
                                       (len list-of-students))) list-of-students)))
        (next-student (caadr (break-at-nth (car (get-random-number-mod-max seed 
                                       (len list-of-students))) list-of-students))))
    (list next-student (append first-part second-part) (cdr (get-random-number-mod-max seed 
                                       (len list-of-students))))
  )
)

;groups-from-list-of-students
; Call using initial-group
; ie (groups-from-list-of-students '("a" "b" "c" "d" "e" "f" "g" "h" "i" "j" "k") (initial-groups 4) 4 0 55235)
;(groups-from-list-of-students (avl-flatten-inner (inner-iterator 3 (get-students-as-data "input.txt"))) (initial-groups 4) 4 0 55235)
(defun groups-from-list-of-students (list-of-students groups num-groups cur-group seed)
  (if (consp list-of-students)
      (let ((first-part (car (break-at-nth (mod cur-group num-groups) groups)))
            (second-part (cdadr (break-at-nth (mod cur-group num-groups) groups)))
            (next-group (caadr (break-at-nth (mod cur-group num-groups) groups)))
            (next-student (car (random-student-from-list list-of-students seed)))
            (next-student-list (cadr (random-student-from-list list-of-students seed)))
            (next-seed (caddr (random-student-from-list list-of-students seed))))
            (groups-from-list-of-students next-student-list 
               (append first-part (list (cons next-student next-group)) second-part)
                num-groups (+ 1 cur-group) seed)
      )
      groups
  )
)

;throw-into-tree-helper
;(throw-into-tree-helper 0 (len (car (groups-from-list-of-students (avl-flatten-inner (inner-iterator 3 (get-students-as-data "input.txt"))) (initial-groups 4) 4 0 55235))) (car (groups-from-list-of-students (avl-flatten-inner (inner-iterator 3 (get-students-as-data "input.txt"))) (initial-groups 4) 4 0 55235)) (empty-tree-inner))
(defun throw-into-tree-helper (i len-list inner-masterlist avl-inner)
  (if (< i (+ (len inner-masterlist) 1))
      (avl-insert-inner (throw-into-tree-helper (+ i 1) len-list (cdr inner-masterlist) avl-inner) (caar inner-masterlist) (cdr (car inner-masterlist)))
      nil))

;throw-into-tree
;(throw-into-tree 0 4 (groups-from-list-of-students (avl-flatten-inner (inner-iterator 3 (get-students-as-data "input.txt"))) (initial-groups 4) 4 0 55235) (empty-tree-inner))
(defun throw-into-tree (i num-groups masterlist avl-inner avl-outer)
  (if (< i num-groups)
      (avl-insert (throw-into-tree (+ i 1) num-groups (cdr masterlist) avl-inner avl-outer) (list i 0) (throw-into-tree-helper 0 (len (car masterlist)) (car masterlist) (empty-tree-inner)))
      nil))

;initial-groups
(defun initial-groups (num-groups)
  (if (not (equal num-groups 0))
      (append (list (list nil)) (initial-groups (- num-groups 1)))
      nil
  )
)

;store-total-loops
(defun store-total-loops (i max)
  (if (< i max)
      (cons 1 (store-total-loops (+ i 1) max))
      nil))

;return-flat-inner-tree
(defun return-flat-inner-tree (i score avl-tree)
  (avl-retrieve avl-tree (list i score))
  )

;return-flat-outer-tree
(defun return-flat-outer-tree (avl-tree)
  (avl-flatten avl-tree)
  )

;return-largest-key-pair
(defun return-worst-and-random-key-pair (avl-tree seed)
  (let ((worst-team (caar (return-flat-outer-tree avl-tree)))
        (rest-of-them (cdr (return-flat-outer-tree avl-tree))))
        (list worst-team (caaadr (break-at-nth 
                                  (car (get-random-number-mod-max seed (len rest-of-them))) rest-of-them)))
  )
)

;return-top-key-pair
(defun return-top-key-pair (avl-tree)
  (caar (return-flat-outer-tree avl-tree)))

;calculate-team-score-temp
(defun calculate-team-score-temp (a b c d)
  (list a (car (cdr '((2 0) 30)))))

;(calculate-team-score (list i 0) (avl-flatten-inner (cdr (avl-retrieve (initialize-teams (+ i 1) master-avl list-of-actual-weights specifications)
;(defun initialize-teams (i num-teams master-avl list-weights spec avl-tree)
;  (avl-insert (avl-delete master-avl (list i 0))
;              (list i (car (cdr (calculate-team-score-temp (list i 0) (avl-flatten-inner (cdr (avl-retrieve master-avl (list i 0)))) list-weights spec))))
;              (cdr (avl-retrieve master-avl (list i 0))))
;  )

;(initialize-teams 0 4 (form-initial-tree (get-students-as-data "input.txt") 4 0 0 23434) '(("SKILL SET" 2/5 ("java" "c/c++" "haskell" "acl2")) ("team interaction skills" 3/5 ("communication and negotiation" "analytic and creative" "organization"))) '(0.3 0.4 0.2 0.8) (empty-tree))
(defun initialize-teams (i num-teams master-avl list-weights spec avl-tree)
  (if (< i num-teams)
      (avl-insert (initialize-teams (+ i 1) num-teams (avl-delete master-avl (list i 0)) list-weights spec avl-tree)
                  (list i (car (cdr (calculate-team-score (list i 0) (avl-flatten-inner (cdr (avl-retrieve master-avl (list i 0)))) list-weights spec))))
                  (cdr (avl-retrieve master-avl (list i 0))))
      nil)
  )

;pull-out-students-from-worst-random
(defun pull-out-students-from-worst-random (seed avl-tree pair)
  (list (keys-inner (cdr (avl-retrieve avl-tree (car pair)))) (keys-inner (cdr (avl-retrieve avl-tree (car (cdr pair)))))))
  ;(avl-retrieve-inner (cdr (avl-retrieve avl-tree (car pair))) "111111113 "))

;combinations-between-worst-random
;(combinations-between-worst-random 40 (empty-tree-inner) (empty-tree-inner) (form-initial-tree (get-students-as-data "input.txt") 4 '(0.3 0.4 0.2 0.8) '(("SKILL SET" 2/5 ("java" "c/c++" "haskell" "acl2")) ("team interaction skills" 3/5 ("communication and negotiation" "analytic and creative" "organization"))) 23434))
(defun combinations-between-worst-random (seed avl-tree)
  (create-all-possible-combinations (car (pull-out-students-from-worst-random seed avl-tree (return-worst-and-random-key-pair avl-tree seed)))
                                    (car (cdr (pull-out-students-from-worst-random seed avl-tree (return-worst-and-random-key-pair avl-tree seed)))))
  )

;simplify
(defun simplify (xs)
  (if (consp xs)
      (append (car xs) (simplify (cdr xs)))
      nil))

;calculate-permutation
;calculates all of the permutations of the two groups you are switching between.
(defun calculate-permutation (permutations avl-tree seed list-weights spec)
  (if (consp permutations)
      (let* ((return-first-inside-tree (cdr (avl-retrieve avl-tree (car (return-worst-and-random-key-pair avl-tree seed))))) ;(first-perm-student))
             (return-second-inside-tree (cdr (avl-retrieve avl-tree (car (cdr (return-worst-and-random-key-pair avl-tree seed))))))
             (1st-student (cdr (avl-retrieve-inner return-first-inside-tree (car (car permutations)))))
             (2nd-student (cdr (avl-retrieve-inner return-second-inside-tree (car (cdr (car permutations))))))
             (new-worst-team (avl-insert-inner (avl-delete-inner return-first-inside-tree (car (car permutations))) 
                                               (car (cdr (car permutations))) 2nd-student))
             (new-random-team (avl-insert-inner (avl-delete-inner return-second-inside-tree (car (cdr (car permutations)))) 
                                          (car (car permutations)) 1st-student)) 
             (new-worst-team-score (calculate-team-score (car (return-worst-and-random-key-pair avl-tree seed)) (avl-flatten-inner new-worst-team) list-weights spec))   
             (new-random-team-score (calculate-team-score (car (cdr (return-worst-and-random-key-pair avl-tree seed))) (avl-flatten-inner new-random-team) list-weights spec)))
             (cons (list (list (car (car permutations)) new-worst-team-score) 
                           (list (car (cdr (car permutations))) new-random-team-score)) 
                     (calculate-permutation (cdr permutations) avl-tree seed list-weights spec))) 
      nil
      )
  )

;get-current-maximum-pair-helper
;helps the get-current-maximum-pair function
(defun get-current-maximum-pair-helper (best list-of-pairs curBest)
  (if (consp list-of-pairs)
      (if (> (cadr (cadaar list-of-pairs)) best)
          (get-current-maximum-pair-helper best (cdr list-of-pairs) (car list-of-pairs))
          (get-current-maximum-pair-helper best (cdr list-of-pairs) curBest)
      )
      curBest
  )
)

;get-current-maximum-pair
;gets the maximum current score of the list-of-pairs
(defun get-current-maximum-pair (list-of-pairs)
  (get-current-maximum-pair-helper (cadar list-of-pairs) (cdr list-of-pairs) nil)
)


;compare-with-original
;compares the old team score to the new team score
(defun compare-with-original (permutations avl-tree seed list-weights spec)
  (cons (calculate-team-score (caar (avl-flatten avl-tree)) (avl-flatten-inner (cdr (car (avl-flatten avl-tree)))) list-weights spec) (calculate-permutation permutations avl-tree seed list-weights spec))
  )

;update-tree-with-new
;go through and update the tree by switching the students around from the permutations
(defun update-tree-with-new (pair avl-tree)
  (let* ((1st-item-original-pair (caar (cdr (car pair))))
         (1st-item-new-score (car (cdr (car (cdr (car pair))))))
         (1st-item-inner-key (caar pair))
         (2nd-item-original-pair (car (car (cdr (car (cdr pair))))))
         (2nd-item-new-score (car (cdr (car (cdr (car (cdr pair)))))))
         (2nd-item-inner-key (caar (cdr pair)))
         (1st-avl-inner-tree (cdr (avl-retrieve avl-tree 1st-item-original-pair)))
         (2nd-avl-inner-tree (cdr (avl-retrieve avl-tree 2nd-item-original-pair)))
         (1st-avl-inner-tree-updated (avl-insert-inner (avl-delete-inner 1st-avl-inner-tree 1st-item-inner-key) 2nd-item-inner-key (cdr (avl-retrieve-inner 2nd-avl-inner-tree 2nd-item-inner-key))))
         (2nd-avl-inner-tree-updated (avl-insert-inner (avl-delete-inner 2nd-avl-inner-tree 2nd-item-inner-key) 1st-item-inner-key (cdr (avl-retrieve-inner 1st-avl-inner-tree 1st-item-inner-key))))
         (avl-main-tree (avl-delete (avl-delete avl-tree 1st-item-original-pair) 2nd-item-original-pair))
         (avl-main-tree-update (avl-insert (avl-insert avl-main-tree (list (car 1st-item-original-pair) 1st-item-new-score) 1st-avl-inner-tree-updated) (list (car 2nd-item-original-pair) 2nd-item-new-score) 2nd-avl-inner-tree-updated))
         ;(new-main-tree         (avl-delete (avl-insert avl-tree (list (car 1st-item-original-pair) 1st-item-new-score)  1st-avl-inner-tree-updated) 1st-item-original-pair))
         ;(new-main-tree-updated (avl-insert new-main-tree (list (car 2nd-item-original-pair) 2nd-item-new-score) 2nd-avl-inner-tree-updated))
         )
   ; 1st-item-original-pair)
   avl-main-tree-update)
  )
    

;create-all-combinations
;takes in the permulations of the two student files that you are switching
;compares the scores of the resulting tree to see if the original tree or the new updated tree is bigger or smaller
;returns the one with the greatest score to attempt to maximize score
(defun create-all-combinations (permutations avl-tree seed list-weights spec)
  (let* ((selection (get-current-maximum-pair (compare-with-original permutations avl-tree seed list-weights spec))))
    (if (not selection)
        avl-tree
        (update-tree-with-new selection avl-tree) ;return updated tree
        )
    )
 ) 

;flatten-inner-tree
;helpter function for the flatten-all-trees - goes through to flatten the inner trees
(defun flatten-inner-tree (the-outer-keys avl-tree)
  (if (consp the-outer-keys)
      (avl-insert (flatten-inner-tree (cdr the-outer-keys) avl-tree) (car the-outer-keys) (avl-flatten-inner (cdr (avl-retrieve avl-tree (car the-outer-keys)))))
      nil)
  )

;flatten-all-trees
;runs through and flattens all of the trees
(defun flatten-all-trees (permutations avl-tree seed list-weights spec)
  (let* ((all-outer-keys (keys avl-tree)))
    (avl-flatten (flatten-inner-tree all-outer-keys avl-tree))))
  
                  
;form-initial-tree
;parameters
;  input:  list-of-students: complete list of all the students
;          list-of-spec: all the parameters that belong to each student
;          seed:  seed for random number generator
;  output: complete avl tree with randomized teams   

;(form-initial-tree (get-students-as-data "input.txt") 4 0 0 23434)
;(form-initial-tree (get-students-as-data "input.txt") 4 '(0.3 0.4 0.2 0.8) '(("SKILL SET" 2/5 ("java" "c/c++" "haskell" "acl2")) ("team interaction skills" 3/5 ("communication and negotiation" "analytic and creative" "organization"))) 23434)
(defun form-initial-tree (list-of-students num-teams list-of-actual-weights specifications seed)
  ;(create-all-combinations
  (flatten-all-trees
   (simplify (combinations-between-worst-random seed 
                                     (initialize-teams 0 
                                                       num-teams 
                                                       (throw-into-tree 0 num-teams (groups-from-list-of-students (avl-flatten-inner (inner-iterator 0 list-of-students)) (initial-groups num-teams) num-teams 0 seed) (empty-tree) (empty-tree-inner))
                                                       list-of-actual-weights
                                                       specifications
                                                       (empty-tree))))
   (initialize-teams 0 
                                                       num-teams 
                                                       (throw-into-tree 0 num-teams (groups-from-list-of-students (avl-flatten-inner (inner-iterator 0 list-of-students)) (initial-groups num-teams) num-teams 0 seed) (empty-tree) (empty-tree-inner))
                                                       list-of-actual-weights
                                                       specifications
                                                       (empty-tree))
   seed
   list-of-actual-weights
   specifications)
 )